package com.yehangtech.algorithm.算法基础篇.第一讲m基础算法._1_快速排序;

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 786. 第k个数
 * <p>
 * 给定一个长度为 n的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k个数。
 * <p>
 * 输入格式
 * 第一行包含两个整数 n和 k。
 * 第二行包含 n个整数（所有整数均在 1∼109范围内），表示整数数列。
 * <p>
 * 输出格式
 * 输出一个整数，表示数列的第 k小数。
 * <p>
 * 数据范围
 * 1≤n≤100000,
 * 1≤k≤n
 * <p>
 * 输入样例：
 * 5 3
 * 2 4 1 5 3
 * 输出样例：
 * 3
 */
public class 第k个数 {

    static int quickSort(List<Integer> list, int left, int right, int k) {
        if (left >= right) {
            return list.get(left);
        }
        int x = list.get(left + right + 1 >> 1);
        int i = left - 1;
        int j = right + 1;
        while (i < j) {
            do i++; while (list.get(i) < x);
            do j--; while (list.get(j) > x);
            if (i < j) {
                int temp = list.get(i);
                list.set(i, list.get(j));
                list.set(j, temp);
            }
        }
        int sl = i - left;
        if (sl >= k) {
            return quickSort(list, left, i - 1, k);
        }
        return quickSort(list, i, right, k - sl);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        int n = in.nextInt();
        int k = in.nextInt();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(in.nextInt());
        }
        System.out.println(quickSort(list, 0, n - 1, k));
    }
}
